// 归并排序;升序;
#include <iostream>
#include <vector>
using namespace std;

void Merge(vector<int> nums,vector<int>& source_nums,int left,int mid,int right){
    // vector 数组要想引用的话,得明确加上&;
    /**
     * 合并两个有序序列片段(两个序列分别是[left,mid],(mid,right]),将结果放到source_nums对应位置;注意这里的位置都是下标从 1 开始的,因此索引数组时要减一;
     * @param nums 待并入source_nums的数组
     * @param source_nums 原始数组
     * @param left 第一个序列的最左位置;
     * @param mid 中间位置;两个有序片段的分界点
     * @param right 第二个序列的最右位置
     * @return 无返回值
     */
    int j,k;
    for (j = mid + 1, k = left; left <= mid && j <= right; k++)
    // j 用于遍历第二个有序的序列;用 left 遍历第一个有序序列;k 用于指向待存放的source_nums的位置
    {
        if (nums[left - 1] < nums[j - 1]) // 注意这里需要减一才是数组的下标
        {
            source_nums[k-1] = nums[left - 1];
            left++;
        }
        else
        {
            source_nums[k-1] = nums[j - 1];
            j++;
        }
    }
    if (left <= mid)
    {
        // 第一个序列还没有遍历完
        for (; left <= mid; left++)
        {
            source_nums[k - 1] = nums[left - 1];
            k++;
        }
    }
    if (j <= right)
    {
        // 第二个序列还没有遍历完
        for (; j <= right; j++)
        {
            source_nums[k - 1] = nums[j - 1];
            k++;
        }
    }
}

vector<int> MergeSort(vector<int> source_nums, vector<int> merge_num, int left, int right)
{
    /**
     * 归并排序(采用递归的方式实现)
     * @param source_nums 原始数组;作用是:从中获取值,仅此而已;
     * @param merge_num 当前递归层中要 merge 入的数组;对应上面 Merge 函数中的source_nums;
     * @param left 待排序的数组的最左位置   
     * @param right 待排序的数组的最右位置
     * @return 返回当前递归层中 merge 后的数组(部分片段经过 merge 后变成有序的);
     */
    if (left == right)
    {
        // 当拆分到最后只剩一个元素时,这个元素就是单独一组;
        merge_num[left - 1] = source_nums[left - 1];
        return merge_num;
    }
    int mid;
    mid = (left + right) / 2;
    vector<int> temp(source_nums.size());
    temp = MergeSort(source_nums, temp, left, mid);
    temp = MergeSort(source_nums, temp, mid + 1, right);
    Merge(temp, merge_num, left, mid, right);
    return merge_num;
}

int main(){
    vector<int> nums = {50, 50, 90, 30, 70, 40, 80, 60, 20};
    nums = MergeSort(nums, nums, 1, nums.size()); // 第二个参数也传入 nums,只是为了让初始的merge_num大小为待排序数组的大小而已

    for (int i = 0; i < nums.size(); i++)
    {
        cout<<nums[i]<<",";
    }
    cout<<endl;
    



    return 0;
}